/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/find-minimum-in-rotated-sorted-array-ii
   @Language: C++
   @Datetime: 16-02-09 05:49
   */

class Solution {
	int findMin(const vector<int> &num,int l,int r){
		if(l>r) return INT_MAX;
		if(num[l]<num[r] || l==r) return num[l];
		int mid = l+(r-l)/2;
		if(num[mid]>num[r]) return findMin(num,l+1,r);
		if(num[mid]<num[l]) return findMin(num,l,mid);
		return min(num[mid],min(findMin(num,l,mid-1),findMin(num,mid+1,r)));
	}
	
public:
	/**
	 * @param num: the rotated sorted array
	 * @return: the minimum number in the array
	 */
	int findMin(vector<int> &num) {
		return findMin(num,0,num.size()-1);
	}
};
